Redondo khởi nghiệp tại CLB quê nhà Argentinos Juniors vào năm 1985, đây cũng là CLB khởi nghiệp của huyền thoại bóng đá người Argentina Diego Maradona. Anh thi đấu ở đây 5 năm trước khi chuyển sang thi đấu cho CLB Tenerife ở Tây Ban Nha. Sau khi chứng kiến phong độ chói sáng của anh tại vòng loại World Cup 1990 và World Cup 1994 trong màu áo tuyển quốc gia Argentina, CLB Hoàng gia Real Madrid đã mua Redondo với giá chuyển nhượng là 5 triệu USD vào năm 1994. Đây là một bước ngoặt đánh dấu sự xuất hiện của một trong số những tiền vệ tài hoa nổi tiếng bậc nhất của bóng đá thế giới.

Real Madrid mua Redondo về để tăng cường sức mạnh trong cuộc đua tới chức vô địch La Liga với F.C. Barcelona được chỉ đạo bởi thuyền trưởng người Hà Lan Johan Cruijff. Redondo đã đáp ứng được mong mỏi của Ban huấn luyện cũng như người hâm mộ Real Madrid khi dẫn dắt Real Madrid giành ngôi vô địch La Liga trước đại kình địch FC Barcelona sau 4 năm bị Barcelona thống trị.

Sự nghiệp của Redondo thăng hoa khi anh cùng Real Madrid đoạt hai chiếc cúp vô địch châu Âu UEFA Champions League danh giá vào năm 1997-1998 và 1999-2000. Trận chung kết Champions League năm 1997-1998, Redondo đã khóa chặt ngòi nổ Zinedine Zidane của Juventus, một trong số những tiền vệ xuất sắc nhất thế giới lúc bấy giờ, góp phần đưa Real Madrid đoạt chức vô địch. Hai năm sau là một mùa giải mà dấu ấn của Redondo đã in đậm trong tâm trí của các cổ động viên Real Madrid lẫn Manchester United. Trong trận bán kết gặp Manchester United tại sân Old Trafford, Redondo đã thực hiện một trong những pha bóng đẹp nhất trong sự nghiệp của mình khi đánh gót vượt qua sự truy cản của hậu vệ Henning Berg trước khi chuyền bóng cho Raul ghi bàn thắng thứ ba cho Real Madrid. Trong trận đấu đó, cái bóng của Redondo đã hoàn toàn che phủ đồng nghiệp của anh bên phía Manchester United, đó chính là Roy Keane, một trong số những tiền vệ xuất sắc của bóng đá thế giới những năm 90. Trong trận chung kết, Real Madrid đã đoạt chức vô địch sau khi vượt qua Valencia. Ở mùa giải Champions League đó, Redondo đã đoạt danh hiệu Cầu thủ xuất sắc nhất.

Tháng 7.2000 ngay sau khi cùng Real Madrid vô địch Champions League, Redondo bất ngờ chuyển đến thi đấu cho A.C. Milan tại Serie A với giá chuyển nhượng là 11 triệu bảng Anh. Tại đây Redondo phải vật lộn với những chấn thương dai dẵng trước khi tuyên bố giải nghệ vào năm 2004 ở độ tuổi 34. Tại Milan, trong giai đoạn nghỉ dưỡng thương (17 tháng), Redondo đã từ chối nhận lương vì lý do không cống hiến được cho CLB (khoảng 4,9 triệu euro).

Anh nói: "Tôi hoàn toàn mãn nguyện với những gì đã thể hiện trên sân cỏ trong nhiều năm qua. Những đội bóng lớn, các trận cầu đỉnh cao và hàng loạt danh hiệu cao quý. Nhưng đã đến lúc tôi phải bù đắp cho gia đình và bạn bè những gì mà họ đáng được hưởng. Tôi rất biết ơn các huấn luyện viên, đồng đội, những người đã luôn ở bên tôi. Tôi sẽ chẳng làm được gì nếu thiếu sự giúp đỡ của họ".